package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.swap

/**
 * Gnome sort is a simple sorting algorithm that works by repeatedly moving an element one position
 * towards its correct position in the sorted part of the array. It does this by comparing adjacent
 * elements and swapping them if they are in the wrong order. This process is continued until the
 * entire array is sorted. The algorithm gets its name from the idea that a gnome always moves the
 * flower pots to put them in the correct order.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.gnomeSort(){
    var i = 1
    var j = 2
    while (i < this.size) {
        if (this[i - 1] < this[i]) {
            i = j++
        } else {
            this.swap(i - 1, i)
            if (--i == 0) {
                i = j++
            }
        }
    }
}